package com.dyz.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class TopKFrequent347 {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        //返回结果集开辟空间
        int [] result = new int[k];
        for(int num : nums){
            hashMap.put(num, hashMap.getOrDefault(num, 0)+1);
        }
        List<Integer>[] list = new ArrayList[nums.length+1];
        //让数字key出现凭次value作为桶的索引index
        for(int num:hashMap.keySet()){
            int i = hashMap.get(num);
            if(list[i]==null){
                list[i] = new ArrayList<>();
            }
            list[i].add(num);
        }
        //从频次最高的第一个不为空的桶开始反向取值
        int i=0, t, j;
        for(t=nums.length; t>0; t--){
            if(list[t]!=null){
                for(j=0;j<list[t].size() && i<k;++j){
                    result[i++]=list[t].get(j);
                }
            }
        }
        return result;
    }
}
